public class Sort {
    public static void mergeSort(int[] array) {
        mergeSortFuc(array,0, array.length-1);
    }

    public static void mergeSortFuc(int[] array,int left,int right) {
        if(left >= right) return;
        int mid = (left + right) / 2;
        mergeSortFuc(array, left, mid);
        mergeSortFuc(array, mid+1, right);
        merge(array,left,right,mid);
    }

    private static void merge(int[] array, int left, int right, int mid) {
        int s1 = left;
        int s2 = mid+1;
        int[] temArr = new int[right-left+1];
        int k = 0;
        while(s1 <= mid && s2 <= right) {
            if(array[s2] <= array[s1]) {
                temArr[k++] = array[s2++];
            }else {
                temArr[k++] = array[s1++];
            }

        }
        while(s1 <= mid) {
            temArr[k++] = array[s1++];
        }
        while(s2 <= right) {
            temArr[k++] = array[s2++];
        }
        for (int i = 0; i < temArr.length; i++) {
            array[i+left] = temArr[i];
        }

    }
}
